package com.demo.sort;

import com.demo.sort.base.SortBase;

/**
 * 选择排序
 * 思路
 * 该思路首先明确选择数前面的子序是已排好序的
 * 选择数(A)   比较数(B)
 * 1. 取出A,对A后的子序进行比较
 * 2. 当A > B 时,记录下标
 * 3. 一次遍历完毕后,进行交换
 * 4. 后面依次类比重复
 * 分析:
 * 时间复杂度    O(n^2)
 * 空间复杂度    O(1)
 *
 * @author huangChao
 **/
public class ChooseSort extends SortBase {

    public int[] sort(int[] init) {
        for(int i = 0, len = init.length - 1; i < len; i++) {
            int minIndex = i;
            for(int j = i + 1; j <= len; j++) {
                if (init[minIndex] > init[j]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                swap(init, i, minIndex);
            }
        }
        return init;
    }
}
